#include <iostream>
#include <queue>
#include <stdio.h>

using namespace std;
typedef struct pos
{
    int step;
    int x, y;
    int rem_k;
    pos (int step, int x, int y, int rem_k)
    {
        this->step = step;
        this->x = x;
        this->y = y;
        this->rem_k = rem_k;
    }
}POS;
int N, K;
bool st[1010][1010];
char maze[1010][1010];
queue<POS> Q;

int res = -1;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool bfs(POS Start)
{
    Q.push(Start);
    st[Start.x][Start.y] = true;
    while(!Q.empty())
    {
        POS now = Q.front();
        Q.pop();
        if (now.x == N - 1 && now.y == N - 1)
        {
            res = now.step;
            return true;
        }

        for (int i = 0; i < 4; i++)
        {
            int x = now.x + dx[i];
            int y = now.y + dy[i];
            int rem_k = now.rem_k;
            if (x <0 || y < 0 || x >= N || y >= N)continue;
            if (maze[x][y] == '#')continue;
            if (maze[x][y] == 'X' && rem_k <= 0) continue;
            if (st[x][y] && rem_k <= 0) continue;

            if (maze[x][y] == '%')
            {
                if (!st[x][y])
                {
                    st[x][y] = true;
                    rem_k = K;
                    Q.push(POS(now.step + 1, x, y, rem_k));
                }
            }
            else
            if (rem_k > 0)
            {
                st[x][y] = true;
                Q.push(POS(now.step + 1, x, y, rem_k - 1));
            } 
            else
            {
                st[x][y] = true;
                Q.push(POS(now.step + 1, x, y, rem_k));
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++)
    {
        scanf("%s", maze[i]);
    }

    if (!bfs(POS(0, 0, 0, 0)))
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n", res);
    }
    return 0;
}